package com.gxc.array;

/**
 * 3101. 交替子数组计数
 给你一个二进制数组nums 。
 如果一个子数组中 不存在 两个 相邻 元素的值 相同 的情况，我们称这样的子数组为 交替子数组 。
 返回数组 nums 中交替子数组的数量。
 */
public class CountAlternatingSubarrays {

    public static void main(String[] args) {
        System.out.println(handle(new int[]{0, 1, 1, 1}));
        System.out.println(handle(new int[]{1, 0, 1, 0}));
    }

    /**
     * dp
     * 如果n-1!= n  则 f(n) = f(n-1) *1 +1
     * 否则 f(n) = 1;
     * sum(n) f(1)....+f(n)
     * @param nums
     * @return
     */
    public static long handle(int[] nums) {
        long res = 0;
        long[] arr = new long[nums.length];
        arr[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i-1]) {
                arr[i] = 1;
            } else {
                arr[i] = arr[i-1] + 1;
            }
        }
        for (int i = 0; i < arr.length; i++) {
            res = res + arr[i];
        }
        return res;
    }

    /**
     * 不适用额外空间
     */
    class Solution {
        public long countAlternatingSubarrays(int[] nums) {
            long res = 0, cur = 0;
            int pre = -1;
            for (int a : nums) {
                cur = (pre != a) ? cur + 1 : 1;
                pre = a;
                res += cur;
            }
            return res;
        }
    }



}
